#-*- encoding=utf-8 -*-

import copy
from collections import deque

#start_state -- 开始状态
#end_state -- 结束状态
#action -- 状态变迁函数 f: state ==> [state,...]
#condition -- 状态约束条件 f: state ==> Ture/False
#solve -- 根据开始状态/结束状态/状态变迁函数/状态约束条件，返回根据深度优先搜索算法求解的状态变迁路径

def solve(start_state, end_state, action, constraint):
	#这里从性能角度应该用hash_set，但是需要提供元素的hash函数映射
	visited_states = [] 				#记录访问过的状态，在状态解空间中搜索目标状态时不允许访问重复状态（去除循环）
	visiting_states = deque() 			#待访问状态列表，后进先出队列（堆栈）实现深度优先搜索算法，其元素为(state,[state])二元组
	start_states = [] 					#[start_state],开始状态列表，记录求解过程中的状态变迁
	start_states.append(start_state)
	visiting_states.append((start_state, start_states))	#把开始状态加入待访问状态队列
	visited_states.append(start_state) 		#加入到待访问队列的
	solved = False #结束搜索标志
	solution = [] #解决方案（状态列表记录状态变迁路径）

	try_times = 0
	while len(visiting_states) > 0 and not solved:
		try_times += 1
		(state, states) = visiting_states.pop()
		if state == end_state:
			solved = True
			solution = states
		else:
			new_states = action(state)
			for s in new_states:
				if constraint(s) and (s not in visited_states):
					next_states = copy.deepcopy(states)
					next_states.append(s)
					visiting_states.append((s, next_states))
					visited_states.append(s)
	print("try_times={}".format(try_times))
	return solution

def print_solution(solution):
	if len(solution) > 0:
		print("find a solution with {} steps: ".format(len(solution)), end='')
		for s in solution:
			print(" =>", s, end='')
		print()
	else:
		print("no solution found!!!")

def farmer_issue_constraint(state):
	#农夫不在时，狼会吃羊，羊会吃白菜
	fake_states = [['F','w','s','C'],['F','w','s','c'],['F','W','s','c'],['f','W','S','C'],['f','W','S','c'],['f','w','S','C']]
	return not(state in fake_states)

def farmer_issue_action(state):
	#农夫一次只能带走一样东西过河
	return_states = []
	for s in state:
		r = copy.deepcopy(state)
		for i in range(len(r)):
			if s == r[i]:
				#农夫不带任何东西过河
				if s == 'F':
					r[i] = 'f'
				elif s == 'f':
					r[i] = 'F'
				#农夫带狼过河
				elif s == 'W':
					r[i] = 'w'
				elif s == 'w':
					r[i] = 'W'
				#农夫带羊过河
				elif s == 'S':
					r[i] = 's'
				elif s == 's':
					r[i] = 'S'
				#农夫带白菜过河
				elif s == 'C':
					r[i] = 'c'
				elif s == 'c':
					r[i] = 'C'
			else:
				#农夫带东西过河时，自己也要过河
				if r[i] == 'F':
					r[i] = 'f'
				elif r[i] == 'f':
					r[i] = 'F'
		return_states.append(r)
	return return_states

def solve_farmer_issue():
	#FWSC的顺序固定，大小写组合变化
	start_state = ['F', 'W', 'S', 'C'] 		#X--表示x在左岸，x--表示x在右岸, x的取值集合为(f,w,s,c)
	end_state = ['f', 'w', 's', 'c'] 		#f--代表farmer，w代表wolf，s代表sheep，c代表cabbage
	solution = solve(start_state, end_state, farmer_issue_action, farmer_issue_constraint)
	print_solution(solution)

def hano_issue_action(state):
	states = []
	for source in range(3):
		for dest in range(3):
			if source != dest:
				if len(state[source]) > 0:
					next_state = copy.deepcopy(state)
					next_state[dest].append(next_state[source].pop())
					states.append(next_state)
	return states

def is_sorted(array):
	i = 0
	n = len(array) - 1
	while i < n:
		if array[i] < array[i+1]:
			return False
		i = i + 1
	return True

def hano_issue_constraint(state):
	for array in state:
		if not is_sorted(array):
			return False
	return True

def solve_hano_issue():
	start_state = [[7, 6, 5, 4, 3, 2, 1], [], []]
	end_state = [[], [], [7, 6, 5, 4, 3, 2, 1]]
	solution = solve(start_state, end_state, hano_issue_action, hano_issue_constraint)
	print_solution(solution)

if __name__ == '__main__':
	solve_farmer_issue()
	solve_hano_issue()
